package com.newegg.research.datastructure;

public class Heap
{
	private Entry[] heapArray;

	private int max_size;

	private int current_size = 0;

	// private int index = 0;
	public Heap(int size)
	{
		max_size = size;
		heapArray = new Entry[max_size];
	}
	
	public void clear()
	{
		heapArray = new Entry[max_size];
		current_size = 0;
	}

	public boolean isEmpty()
	{
		return current_size == 0;
	}

	public Heap()
	{
		this(16);
	}

	public int size()
	{
		return current_size;
	}

	private synchronized void increaseArray()
	{
		Entry[] newHeapArray = new Entry[max_size * 2];
		System.arraycopy(heapArray, 0, newHeapArray, 0, current_size);
		max_size = max_size << 1;
		heapArray = newHeapArray;
	}

	public boolean insert(Object o, float p)
	{
		if (o == null)
			return false;

		if (current_size == max_size)
			increaseArray();

		Entry e = new Entry(o, p);

		heapArray[current_size] = e;
		trickleUp(current_size++);
		// current_size++;
		return true;
	}

	public Object remove()
	{
		Entry e = removeEntry();
		if (e != null)
			return e.value;
		else
			return e;
	}

	public Entry removeEntry()
	{
		if (isEmpty())
			return null;

		Entry top = heapArray[0];

		if (top == null)
			return top;
		heapArray[0] = heapArray[--current_size];
		trickleDown(0);
		// current_size--;
		return top;
	}

	public void trickleUp(int index)
	{
		Entry bottom = heapArray[index];
		int parent = getParent(index);
		boolean swapped = false;
		while (index > 0
				&& heapArray[parent].getPriority() < bottom.getPriority())
		{
			swapped = true;
			heapArray[index] = heapArray[parent];
			index = parent;
			parent = getParent(parent);
		}
		if(swapped)
			heapArray[index] = bottom;
	}

	public void trickleDown(int index)
	{
		Entry top = heapArray[index];
		while (hasChild(index))
		{
			int leftChild = getLeftChild(index);
			int rightChild = getRightChild(index);
			int largerChild = leftChild;

			if (rightChild < current_size
					&& heapArray[rightChild].getPriority() > heapArray[leftChild]
							.getPriority())
				largerChild = rightChild;
			if (heapArray[largerChild].getPriority() <= top.getPriority())
			{
				// heapArray[largerChild] = top;
				// return ;
				break;
			} else
			{
				heapArray[index] = heapArray[largerChild];
				index = largerChild;
			}
		}
		heapArray[index] = top;
	}

	public int getParent(int index)
	{
		return (index - 1) / 2;
	}

	public boolean hasChild(int index)
	{
		return index < current_size / 2;
	}

	public int getLeftChild(int index)
	{
		return 2 * index + 1;
	}

	public int getRightChild(int index)
	{
		return 2 * index + 2;
	}

	public void debug()
	{
		System.out.println("heapArray:");
		for (int i = 0; i < current_size; i++)
		{
			Object o = heapArray[i];
			System.out.println(o);
		}
		System.out.println("===============================");
	}

	public static void main(String[] args)
	{
		Heap heap = new Heap(10);
		heap.insert(1, (float)0.9925221498799204);
		heap.debug();
		heap.insert(2, (float)0.9700143377667297);
		heap.debug();
		heap.insert(3, (float)0.9927930845086522);
		heap.debug();
		heap.insert(4, (float)0.9856608530858693);
		heap.debug();
//		heap.insert(2, 2);
		// heap.insert(3, 3);
		// heap.insert(4, 4);
		// for (int i = 60; i > 0; i--)
		// {
		// heap.insert(i, i);
		// }
		
		System.out.println();
		while (!heap.isEmpty())
		{
			System.out.println(heap.remove());
		}
	}

	public static class Entry
	{
		private Object value;

		private float priority;

		public Entry(Object value, float priority)
		{
			this.value = value;
			this.priority = priority;
		}

		public float getPriority()
		{
			return priority;
		}

		public void setPriority(float priority)
		{
			this.priority = priority;
		}

		public Object getValue()
		{
			return value;
		}

		public void setValue(Object value)
		{
			this.value = value;
		}

		public String toString()
		{
			return this.priority + ":" + this.value.toString();
		}
	}
}
